home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 18 / CU Amiga Magazine's Super CD-ROM 18 (1997)(EMAP Images)(GB)[!][issue 1998-01].iso / CUCD / Programming / AmigaE / Src / Various / radix.e < prev    next >
Text File  |  1994-11-08  |  2KB  |  109 lines
  1. /* Super fast sort program.
  2.    whereas slow methods like quicksort/mergesort use O(n * log n) methods,
  3.    radixsort is a true O(n) method. Especially for large textfiles, it is a
  4.    LOT faster than other sorters (a log order of magnitude ;-).
  5.    Radixsort uses a 256 buckets at each level to put the strings in. arrays
  6.    of buckets are only allocated when the number of strings left to sort is
  7.    large.
  8.    Radix.e reads from a file, and outputs to stdout.
  9. */
  10.  
  11. MODULE 'tools/file', 'tools/exceptions'
  12.  
  13. DEF rad1:PTR TO LONG,radsize:PTR TO LONG
  14.  
  15. OBJECT str
  16.   next,data
  17. ENDOBJECT
  18.  
  19. PROC main() HANDLE
  20.   DEF m,l,n,list
  21.   m,l:=readfile(arg)
  22.   n:=countstrings(m,l)
  23.   list:=stringsinfilenolist(m,l,n)
  24.   doradix(NEW rad1[256],NEW radsize[256],list,n)
  25.   restradix(rad1,radsize)
  26. EXCEPT
  27.   report_exception()
  28. ENDPROC
  29.  
  30. PROC doradix(table:PTR TO LONG,size:PTR TO LONG,str:PTR TO LONG,num)
  31.   DEF a,s,c
  32.   FOR a:=1 TO num
  33.     s:=str[]++
  34.     c:=s[]
  35.     table[c]:=NEW [table[c],s]:str
  36.     size[c]:=size[c]+1
  37.   ENDFOR
  38. ENDPROC
  39.  
  40. PROC restradix(table:PTR TO LONG,size:PTR TO LONG,level=1)
  41.   DEF a
  42.   FOR a:=0 TO 255 DO recradix(table[]++,size[]++,level)
  43. ENDPROC
  44.  
  45. PROC recradix(l:PTR TO str,num,level)
  46.   DEF tab:PTR TO LONG,size:PTR TO LONG,s,c,temp:PTR TO str
  47.   IF num
  48.     IF num<20
  49.       straight(l,num)
  50.     ELSE
  51.       NEW tab[256],size[256]
  52.       WHILE l
  53.         s:=l.data
  54.         temp:=l
  55.         l:=l.next
  56.         c:=s[level]
  57.         temp.next:=tab[c]
  58.         tab[c]:=temp
  59.         size[c]:=size[c]+1
  60.       ENDWHILE
  61.       restradix(tab,size,level+1)
  62.       END tab[256],size[256]
  63.     ENDIF
  64.   ENDIF
  65. ENDPROC
  66.  
  67. PROC straight(l:PTR TO str,num)            -> sort these with a silly method
  68.   DEF a,tl:PTR TO str,best:PTR TO str,fbest
  69.   fbest:=[NIL,[$7F7F7F7F,$7F7F7F7F,$7F7F7F7F,0]:LONG]:str
  70.   FOR a:=1 TO num
  71.     tl:=l
  72.     best:=fbest
  73.     WHILE tl
  74.       IF tl.data THEN IF OstrCmp(best.data,tl.data)=-1 THEN best:=tl
  75.       tl:=tl.next
  76.     ENDWHILE
  77.     IF best<>fbest
  78.       PutStr(best.data)
  79.       FputC(stdout,"\n")
  80.       best.data:=NIL
  81.     ENDIF
  82.   ENDFOR
  83. ENDPROC
  84.  
  85. PROC stringsinfilenolist(mem,len,max)    -> to eliminate 32k strings boundary
  86.   DEF list:PTR TO LONG,l
  87.   NEW list[max]
  88.   MOVE.L list,A1
  89.   MOVE.L max,D3
  90.   MOVE.L mem,A0
  91.   MOVE.L A0,D1
  92.   ADD.L  len,D1
  93.   MOVEQ  #0,D0
  94.   MOVEQ  #10,D2
  95. stringsl:
  96.   CMP.L  D3,D0
  97.   BPL.S  done
  98.   ADDQ.L #1,D0
  99.   MOVE.L A0,(A1)+
  100. findstringl:
  101.   CMP.B  (A0)+,D2
  102.   BNE.S  findstringl
  103.   CLR.B  -1(A0)
  104.   CMPA.L D1,A0
  105.   BMI.S  stringsl
  106. done:
  107.   MOVE.L D0,l
  108. ENDPROC list,l
  109.